package grafo.algoritmo;

import grafo.estrutura.Adjacente;
import grafo.estrutura.Aresta;
import grafo.estrutura.ListaAresta;
import grafo.estrutura.ListaVertice;
import grafo.estrutura.Vertice;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Iterator;

public class Grafo implements Serializable{
	 // Listas de vÔøΩrtices e arestas
    private ListaVertice vertices;
    private ListaAresta arestas;
    // Indicador de grafo direcional
    private Boolean direcional;

    public Grafo(Boolean aDirecional)
    {
        vertices = new ListaVertice();
        arestas = new ListaAresta();
        direcional = aDirecional;
    }

    public Vertice adicionarVertice(int aID, String aDescricao)
    {
        // Adiciona e retorna um vÔøΩrtice
        return vertices.adicionarVertice(aID, aDescricao);
    }

    public Aresta adicionarAresta(int aID, String aDescricao, 
        Vertice aVerticeOrigem, Vertice aVerticeDestino, double aGanho)
    {
        // Adiciona uma aresta
        Aresta a = arestas.adicionarAresta(aID, aDescricao, aVerticeOrigem, aVerticeDestino, aGanho);
        // Adiciona um adjacente ao vÔøΩrtice origem
        aVerticeOrigem.adicionarAdjacente(aVerticeDestino, a);
        // Se nÔøΩo direcional, adiciona um adjacente ao vÔøΩrtice destino
        if (!direcional && aVerticeOrigem != aVerticeDestino) aVerticeDestino.adicionarAdjacente(aVerticeOrigem, a);
        // Retorna a aresta
        return a;
    }

    public String imprimirListaAdjacencias()
    {
        String s = "";
        for (Vertice v : vertices)
        {
            s += v.getDescricao() + " ";
            for (Adjacente adj : v.getAdjacentes())
                s += adj.getVertice().getDescricao() + "/" + adj.getAresta().getGanho() + " ";
            s = s + "\n";
        }        
        return s;
    }
    
    public Grafo clonar()
    {
    	// Instancia grafo clonado
    	Grafo c = new Grafo(direcional);
    	
    	// Percorre os vÔøΩrtices do grafo original
    	for (Vertice v : vertices)
    		// Adiciona o vÔøΩrtice no grafo clonado
    		c.adicionarVertice(v.getID(), v.getDescricao());
    	
    	// Percorre as arestas do grafo original
    	for (Aresta a : arestas)
    	{
    		// IDs dos vÔøΩrtices origem e destino
    		int id_orig = a.getVerticeOrigem().getID();
    		int id_dest = a.getVerticeDestino().getID();
    		
    		// Recupera o vÔøΩrtice do grafo clonado com id_orig
    		Vertice orig = c.vertices.selecionar(id_orig);
    		
    		// Recupera o vÔøΩrtice do grafo clonado com id_dest
    		Vertice dest = c.vertices.selecionar(id_dest);
    		
    		// Adiciona a aresta no grafo clonado
    		c.adicionarAresta(a.getID(), a.getDescricao(), orig, dest, a.getGanho());
    	}
        	
    	// Retorna o grafo clonado
    	return c;
    }
    
    public boolean removerAresta(Aresta a)
    {
    	// Vertices adjacentes
    	Vertice aVerticeOrigem = a.getVerticeOrigem();
    	Vertice aVerticeDestino = a.getVerticeDestino();
    	
    	// Remove adjacente do vÔøΩrtice origem
    	aVerticeOrigem.removerAdjacente(aVerticeDestino, a);
    	
    	// Se nÔøΩo direcional, adiciona um adjacente ao vÔøΩrtice destino
    	if (!direcional && aVerticeOrigem != aVerticeDestino) aVerticeDestino.removerAdjacente(aVerticeOrigem, a);
   	
    	// Remove a aresta
    	return arestas.remove(a);
    }
    
    public boolean removerVertice(Vertice v)
    {
    	int i = 0;
    	// Remove as arestas ligadas ao vÔøΩrtice
    	while (i < arestas.size())
    	{
    		Aresta a = arestas.get(i);
    		if (a.getVerticeOrigem() == v || a.getVerticeDestino() == v)
    		{
    			removerAresta(a);
    		}
    		else i++;
    	}
    	// Remove o vÔøΩrtice
    	return vertices.remove(v);
    }
    
    public void removerLacos()
    {
    	int i = 0;
    	// Remove as arestas ligadas a um vÔøΩrtice
    	while (i < arestas.size())
    	{
    		Aresta a = arestas.get(i);
    		if (a.getVerticeOrigem() == a.getVerticeDestino())
    		{
    			removerAresta(a);
    		}
    		else i++;
    	}
    }
    
    public void fundirVertices(Vertice v, Vertice w)
    {
    	// Remove as arestas ligando os vÔøΩrtices v e w
    	int i = 0;
    	while (i < arestas.size())
    	{
    		Aresta a = arestas.get(i);
    		if ( (a.getVerticeOrigem() == v && a.getVerticeDestino() == w) ||
    			 (a.getVerticeOrigem() == w && a.getVerticeDestino() == v) )
    		{
    			removerAresta(a);
    		}
    		else i++;
    	}
    	// Substitui o vÔøΩrtice w pelo v em todas arestas
    	for (Aresta a : arestas)
    		a.substituirVertice(v, w);
    	// Substitui o vÔøΩrtice w pelo v em todas listas de adjacentes
    	for (Vertice x : vertices)
    		x.substituirAdjacente(v, w);
    	// Copia os adjacentes de w para v
    	v.copiarAdjacentes(w);
    	// Remove o vÔøΩrtice w
    	removerVertice(w);
    }
    
    public ListaVertice getVertices() {
    	return this.vertices;
    }
   
    
    //==========
    public boolean verificarConexidade(){
		int c = 0;
		Grafo H = clonar();

		while(!H.vertices.isEmpty()){

			Vertice v = H.vertices.get(H.vertices.size()-1);
			while(!v.getAdjacentes().isEmpty()){
				H.fundirVertices(v, v.getAdjacentes().get(v.getAdjacentes().size()-1).getVertice());
			}
			H.removerVertice(v);
			c++;

		}

		if (c>1)
			return false;
		else
			return true;
	}

	public ArrayList<Grafo> getSubgrafos(Grafo g){
		int c = 0;
		Grafo H = g.clonar();
		Grafo h = g.clonar();
		ArrayList<Grafo> s = new ArrayList<Grafo>();
		while(!H.vertices.isEmpty()){
			Grafo t = new Grafo(H.direcional);
			Vertice v = H.vertices.get(H.vertices.size()-1);
			t.vertices.add(h.vertices.get(H.vertices.size()-1));
			while(!v.getAdjacentes().isEmpty()){
				int ultimo = v.getAdjacentes().size()-1;
				int id_dest = v.getAdjacentes().get(ultimo).getVertice().getID();

				t.vertices.add(h.vertices.selecionar(id_dest));
				t.arestas.add(v.getAdjacentes().get(ultimo).getAresta());

				H.fundirVertices(v, v.getAdjacentes().get(v.getAdjacentes().size()-1).getVertice());
			}

			H.removerVertice(v);

			s.add(t);
			c++;

		}

		return s;
	}
	
	public ListaVertice FTD(Vertice v) {
		ListaVertice listaFTD = new ListaVertice();
		String str;

		recFTD(v, listaFTD);

		Iterator<Vertice> itr = listaFTD.iterator();
		str = "(" + v.getDescricao() + ") = " + "{";
		while(itr.hasNext()) {
			str += itr.next().getDescricao() + ", ";
		}
		str += "}";

		return listaFTD;
	}

	private void recFTD(Vertice v, ListaVertice listaFTD) {
		Iterator<Adjacente> itr = v.getAdjacentes().iterator();

		while (itr.hasNext()) {
			Vertice vTemp = itr.next().getVertice();
			if (!listaFTD.contains(vTemp)) {
				listaFTD.add(vTemp);
				recFTD(vTemp, listaFTD);
			}
		}
	}

	public ListaVertice FTI(Vertice v){
		ListaVertice listaFTI = new ListaVertice();
		Iterator<Aresta> itr = arestas.iterator();

		while(itr.hasNext()){
			Vertice from = itr.next().getVerticeOrigem();
			if(FTD(from).contains(v) && !listaFTI.contains(from))
				listaFTI.add(from);
		}

		return listaFTI;
	}
	
	public Grafo grafoReduzido() {
		int R[][] = new int[vertices.size()][vertices.size()];
		int Q[][] = new int[vertices.size()][vertices.size()];
		int RQ[][] = new int[vertices.size()][vertices.size()];
		
		Grafo reduzido = this.clonar();
		
		for(Vertice i: vertices) {
			for (Vertice j: vertices) {
				if (FTI(j).contains(i)) {
					R[vertices.indexOf(i)][vertices.indexOf(j)] = 1;
					Q[vertices.indexOf(i)][vertices.indexOf(j)] = 1;
				} else {
					R[vertices.indexOf(i)][vertices.indexOf(j)] = 0;
					Q[vertices.indexOf(i)][vertices.indexOf(j)] = 0;
				}
			}
		}
		
		//matriz transposta
		int row, col, tmp;  
	    for (int i=0; i<Q.length*Q.length-1; i++) {  
	        row = i%Q.length;  
	        col = i/Q.length;  
	        tmp = Q[row][col];  
	        Q[row][col] = (col > row ? Q[col][row] : Q[row][col]);  
	        Q[col][row] = (col > row ? tmp : Q[col][row]);  
	    }
	    
	    //xnor
	    for(int i=0; i < R.length; ++i) {
			for (int j=0; j < R.length; ++j) {
				if (R[i][j] == Q[i][j]) {
					RQ[i][j] = 1;
				} else {
					RQ[i][j] = 0;
				}
			}
		}
	    
	    //removendo linhas duplicadas
	    for(int i=0; i < RQ.length -1; ++i) {
			for (int j=i +1; j < RQ.length; ++j) {
				int cont = 0;
				for (int k=0; k < RQ.length; ++k) {
					if (RQ[i][k] == RQ[j][k]) {
						++cont;
					}
					
					if (cont == RQ.length) {
						for (int z=0; z < RQ.length; ++z) {
							RQ[j][z] = 0;
						}
					}
				}
			}
		}
	    
	    //criando lista de vertices para fundir
	    ArrayList<Vertice> listaV = new ArrayList<Vertice>();
	    for(int i=0; i < RQ.length; ++i) {
			for (int j=0; j < RQ.length; ++j) {
				if (RQ[i][j] == 1) {
					listaV.add(reduzido.vertices.get(i));
					listaV.add(reduzido.vertices.get(j));
				}
			}
	    }
	    
	    //fundindo - BUG (Tenta fundir vertices ja fundidos - funciona para grafos que necessitam de apenas 1 fusao por vertice)
	    Iterator<Vertice> i = listaV.iterator();
	    while (i.hasNext()) {
	    	Vertice v1 = i.next();
	    	Vertice v2 = i.next();
	    	if (v1.getID() != v2.getID()) {
	    		reduzido.fundirVertices(v1, v2);
	    	}
	    }
	    
		return reduzido;
	}
	
	public boolean verificarGrafoEuleriano(){
		if (verificarConexidade())
			for (Vertice v : vertices) 
				if (v.getAdjacentes().size()%2 != 0)
					return false;
		return true;
	}

	//Fleury
	public ListaVertice getCicloEuleriano(){

		if (verificarGrafoEuleriano()){
			Grafo G = clonar();
			Vertice v0 = vertices.get(0);
			ListaVertice C = new ListaVertice();
			C.add(v0);

			while (!G.arestas.isEmpty()){
				Vertice vi = G.vertices.selecionar(C.get(C.size()-1).getID());
				Vertice des = null;
				if (vi.getAdjacentes().size()==1){
					Aresta ai = vi.getAdjacentes().get(0).getAresta();
					des = ai.getVerticeDestino();
					if (ai.getVerticeDestino() == vi)
						des = ai.getVerticeOrigem();
					G.removerAresta(ai);
				}
				else
					for (int i=0 ; i<vi.getAdjacentes().size() ; i++){
						Adjacente ad = vi.getAdjacentes().get(i);
						Aresta ai = ad.getAresta();
						des = ai.getVerticeDestino();
						if (des == vi)
							des = ai.getVerticeOrigem();
						G.removerAresta(ai);
						if (G.verificarConexidade())
							break;
						else
							G.adicionarAresta(ai.getID(), ai.getDescricao(), ai.getVerticeOrigem(), ai.getVerticeDestino(), ai.getGanho());
					}

				for (int i=0 ; i<G.vertices.size() ; i++) 
					if (G.vertices.get(i).getAdjacentes().size() == 0)
						G.removerVertice(G.vertices.get(i));


				C.add(vertices.selecionar(des.getID()));
			}
			return C;
		}
		return null;
	}
	
	public String imprimirMatrizCusto() {
		String s = "";
		boolean achou = false;
        for (Vertice v : vertices) {
            for (Vertice j: vertices) {
            	for (Adjacente adj : v.getAdjacentes()) {
            		if (adj.getVertice() == j) {
            			achou = true;
                		s += adj.getAresta().getGanho() + " ";
                	}
            	}
            	if (!achou) {
            		s += "0.0 ";
            	}
            	achou = false;
            }
            s = s + "\n";
        }        
        return s;
	}
	
	//PROVA 2
	public ListaVertice carteiroChines() {
		if (this.verificarGrafoEuleriano()) {
			return this.getCicloEuleriano();
		}
		return null;
	}

	public ListaAresta getArestas() {
		return arestas;
	}

}
